package com.leetcode.algs4.graph.mst;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/6/18 19:22
 */
public class LazyPrimMST {
    private boolean[] marked;   // mst的所有顶点
    private Queue<Edge> mst; //mst的所有边
    private PriorityQueue<Edge> pq; // 横切边 -- 包括失效的边

    public LazyPrimMST(EdgeWeightGraph G) {
        pq = new PriorityQueue<>();
        marked = new boolean[G.V()];
        mst = new LinkedList<>();

        /**
         * mst中的所有边都是从pq加入的
         * pq作为中介数据结构，主要是提供权重最小的边 -- 队首
         */

        visit(G, 0); //从起点开始，先将所有邻接边入队
        while (!pq.isEmpty()) {
            Edge edge = pq.poll(); // 从pq中得到权重最小的边
            int v = edge.either(), w = edge.other(v);
            if (marked[v] && marked[w]) continue; // 跳过失效的边 -- 两个已经加入的MST的点，不会再构成边
            // 将满足条件的边加入mst中
            mst.offer(edge);
            if (!marked[v]) visit(G, v);
            if (!marked[w]) visit(G, w);
        }
    }

    public void visit(EdgeWeightGraph G, int v) {
        marked[v] = true;
        for (Edge edge : G.adj(v)) {
            if (marked[edge.other(v)]) pq.offer(edge);
        }
    }

    public Iterable<Edge> edges() {
        return mst;
    }

    // 返回最小权值
    public double weight() {
        // 一个流搞定
        return mst.stream().mapToDouble(Edge::weight).sum();
    }

}
